package addtwonumbersii445

// 实现 两数相加 II https://leetcode.cn/problems/add-two-numbers-ii/
// 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
//
// 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
/**
 * 思路：
 * 1. 先遍历链表 l1 和 l2，分别将它们的值存入栈 stack1 和 stack2 中。
 * 2. 然后从栈中弹出元素，进行相加，注意进位的处理。
 * 3. 最后将结果存入一个新的链表中，返回这个链表。
 * 4. 注意链表的头节点需要特殊处理。
 * 5. 时间复杂度 O(max(m, n))，空间复杂度 O(max(m, n))，其中 m 和 n 分别是链表 l1 和 l2 的长度。
 * 6. 注意：这里的链表是单向链表，所以我们需要使用栈来存储链表的值。
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	stack1 := make([]int, 0)
	stack2 := make([]int, 0)

	// 遍历链表 l1 和 l2，将它们的值存入栈 stack1 和 stack2 中
	for l1 != nil {
		stack1 = append(stack1, l1.Val)
		l1 = l1.Next
	}
	for l2 != nil {
		stack2 = append(stack2, l2.Val)
		l2 = l2.Next
	}

	// 搞一个虚拟的头结点
	dummy := &ListNode{}
	carry := 0

	// 从栈中弹出元素，进行相加，注意进位的处理
	for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
		sum := carry
		if len(stack1) > 0 {
			sum += stack1[len(stack1)-1]
			stack1 = stack1[:len(stack1)-1]
		}
		if len(stack2) > 0 {
			sum += stack2[len(stack2)-1]
			stack2 = stack2[:len(stack2)-1]
		}
		carry = sum / 10
		node := &ListNode{Val: sum % 10}
		node.Next = dummy.Next
		dummy.Next = node
	}

	return dummy.Next
}
